package fun.coding.leetcode;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

public class ThreeSum {

	public static void main(String[] args) {
		ThreeSum ins = new ThreeSum();
		int[] test1 = {-1, 0, 1, 2, -1, -4};
		LeetCodeHelpers.printListOfList(ins.threeSum(test1));
		
		System.out.println();
		int[] test2 = {-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6};
		LeetCodeHelpers.printListOfList(ins.threeSum(test2));
	}

	// This has to be a O(N^2) solution, my original thought won't since it will omit solutions
	// My original thought is keep a start, and end, and look through the number in between, and l++, r--
	public List<List<Integer>> threeSum(int[] num) {
		List<List<Integer>> res = new LinkedList<List<Integer>>();
		
		if (num == null || num.length < 3) return res;
		
		Arrays.sort(num);
		
		for (int i = 0; i < num.length; i++) {
			int target = num[i];
			
			int l = i + 1;
			int r = num.length - 1;
			
			while (l < r) {
				int left = num[l];
				int right = num[r];
				
				int sum = left + right;
				if (sum == -1*target) {
					List<Integer> t = new LinkedList<Integer>();
					t.add(target);
					t.add(left);
					t.add(right);
					res.add(t);
					while (l < num.length && num[l] == left) {
						l++;
					}
					
					while (r >= 0 && num[r] == right) {
						r--;
					}
					
				} else if (sum > -1*target) {
					// here I could also directly r--, since if it is not a solution, doesn't matter here
					/*
					while (r >= 0 && num[r] == right) {
						r--;
					}
					*/
					r--;
				} else {
					l++;
				}
			}
			// skipping dups
			while (i + 1 < num.length && num[i] == num[i + 1]) i++;
		}
		return res;
	}
	
}
